High speed packet networks, such as Asynchronous Transfer Mode (ATM) networks, support connections to multiple sessions which operate at different packet transfer rates. Packet scheduling must be handled such that packets are transferred from the different sessions with minimal delays, while maximizing the use of available bandwidth. Ideally, a scheduler should fairly arbitrate packets for delivery while being cost effective to implement. Many schedulers are known which are either simple to implement but do not fairly arbitrate between packets of different sessions, or provide fair arbitration but are costly to implement. A class of schedulers known as Packet Fair Queuing (PFQ) schedulers (described below) are cost effective to implement and include Virtual Clock (VC) schedulers, Self Clocked Fair Queuing (SCFQ) schedulers, Start Time Fair Queuing (STFQ) schedulers and Deficit Round Robin Fair Queuing (DRRFQ) schedulers.
VC schedulers provide every session with a guaranteed throughput. Each user requests an allocation for the amount of traffic the user expects. The packets are then time stamped and placed in a queue according to the value of their time stamp. One drawback to this method is there is no way to detect or correct errors. VC schedulers have a tight delay bound that is independent of the number of sessions involved in order to provide for delay minimization, however, VC schedulers do not allocate available bandwidth as fairly as some other schedulers.
Self Clocked Fair Queuing (SCFQ) schedulers as well as Start Time Fair Queuing (STFQ) schedulers have a high degree of fairness for allocating bandwidth. However, they do not have the desired delay minimization since the virtual time is not strictly monotonically increasing, and their delay bounds are proportional to the number of sessions involved. DRRFQ schedulers have a degree of fairness but are less effective when load balancing or distributed queues are used.
Other types of PFQ schedulers, such as Worst-case Fair Weighted Fair Queuing (WF.sup.2 Q), Worst Case Fair Weighted Fair Queuing Plus (WF.sup.2 Q+) and Packetized Generalized Processor Sharing (PGPS) offer better performance but are more costly to implement than the SCFQ, STFQ and DRRFQ schedulers.
The WF.sup.2 Q and WF.sup.2 Q+ schedulers have both a high degree of fairness, effectively minimize scheduling delay through the scheduler and have a tight delay bound that is independent of the number of sessions involved. The implementation costs of WF.sup.2 Q and WF.sup.2 Q+ schedulers however are high compared to other schedulers since the WF.sup.2 Q and WF.sup.2 Q+ schedulers must perform two searches on each session, one search for determining the packet start times of the first packet in each session and another search for determining the packet start times of the backlogged packets in each session. Other schedulers typically perform only a single search of the first packet of each session to determine the packet start times for each such packet.
PGPS schedulers are similar to the WF.sup.2 Q and WF.sup.2 Q+ schedulers, especially when utilizing packets having a small packet size, however the PGPS schedulers are better at minimizing worst-case session delay; that is, the amount of time a session has to wait before it can schedule a packet for transfer.
Accordingly, it would be desirable to have a scheduler which is cost effective to implement and which is capable of scheduling the transmission of packets from different sessions such that the individual demands on throughput and delay can be met in a fair and efficient manner.